package com.lwl.Algorithmic_data_structure.class22暴力递归2动态规划5;

import com.lwl.Utils.PrintUtil;

/**
 * @author lwl
 * @Description 给你一个数字，请你求出可以裂开的不同方式；必须要前面的数比后面的要小
 * @date 2023/6/13 22:05
 */
public class Code03SplitNumber {

    public static void main(String[] args) {
        // 1 1 1
        // 1 2
        // 3
        System.out.println(splitNumber(3));
        System.out.println(splitNumber2(3));
//        System.out.println(splitNumber(10));
//        System.out.println(splitNumber2(10));
//        System.out.println(splitNumber(11));
//        System.out.println(splitNumber2(11));
//        System.out.println(splitNumber(12));
//        System.out.println(splitNumber2(12));
//        System.out.println(splitNumber(13));
//        System.out.println(splitNumber2(13));
    }

    static public int splitNumber2(int num) {
        int[][] dp = new int[num + 1][num + 2];
        for (int i = 0; i <= num + 1; i++) {
            dp[0][i] = 1;
        }
        for (int rest = 1; rest <= num; rest++) {
            for (int splitNum = rest; splitNum >= 1; splitNum--) {
                int ans = 0;
                for (int i = 0; i <= (rest / splitNum); i++) {
                    ans += dp[rest - (i * splitNum)][splitNum + 1];
                }
                dp[rest][splitNum] = ans;
            }
        }
        PrintUtil.printArray(dp);
        return dp[num][1];
    }

    static public int splitNumber(int num) {
        return process(num, 1);
    }

    private static int process(int rest, int splitNum) {
        if (rest <= 0 || splitNum > rest) {
            return rest == 0 ? 1 : 0;
        }
        int ans = 0;
        for (int i = 0; i <= (rest / splitNum); i++) {
            ans += process(rest - (i * splitNum), splitNum + 1);
        }
        return ans;
    }

}
